//
//  BinarySearchTree.hpp
//  BinarySearchTree
//
//  Created by 卜绎皓 on 2022/11/7.
//

#pragma once
#include<iostream>
using namespace std;

namespace KEY
{
    template<class K>
    struct BSTreeNode
    {
        BSTreeNode<K>* _left;
        BSTreeNode<K>* _right;
        K _key;

        BSTreeNode(const K& key)
            : _left(nullptr)
            , _right(nullptr)
            , _key(key)
        {}
    };
    template<class K>
    class BSTree
    {
        typedef BSTreeNode<K> Node;
    public:
        bool Insert(const K& key)
        {
            //空树,直接插入
            if (_root == nullptr)
            {
                _root = new Node(key);
                return true;
            }
            //查找要插入的位置
            Node* parent = nullptr;
            Node* cur = _root;
            while (cur)
            {
                if (cur->_key < key)//往右子树查找
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if (cur->_key > key)//往左子树查找
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else
                {
                    return false;//默认不支持冗余
                }
            }
            //new节点,这里需要在BSTreeNode补构造函数
            cur = new Node(key);
            if (parent->_key < cur->_key)//新节点链接到父的左还是右,还需要再比一次
            {
                parent->_right = cur;//关联
            }
            else
            {
                parent->_left = cur;//关联
            }
            return true;
        }
        Node* Find(const K& key)
        {
            Node* cur = _root;
            while (cur)
            {
                if (cur->_key < key)
                {
                    cur = cur->_right;
                }
                else if (cur->_key > key)
                {
                    cur = cur->_left;
                }
                else
                {
                    return cur;
                }
            }
            return nullptr;
        }
        bool Erase(const K& key)
        {
            Node* parent = nullptr;
            Node* cur = _root;
            while (cur)
            {
                if (cur->_key < key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if (cur->_key > key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else
                {
                    //删除
                    if (cur->_left == nullptr)//ab
                    {
                        //没有父亲
                        if (cur == _root)
                        {
                            _root = cur->_right;//右作根
                        }
                        else
                        {
                            //确定目标位置父亲的左还是右和目标位置的孩子关联(目标位置的左右孩子在外层if已经确定了)
                            if (cur == parent->_left)
                            {
                                parent->_left = cur->_right;
                            }
                            else
                            {
                                parent->_right = cur->_right;
                            }
                        }
                        delete cur;
                    }
                    else if (cur->_right == nullptr)//ac
                    {
                        //没有父亲
                        if (cur == _root)
                        {
                            _root = cur->_left;
                        }
                        else
                        {
                            //确定目标位置父亲的左还是右和目标位置的孩子关联(目标位置的左右孩子在外层if已经确定了)
                            if (cur == parent->_left)
                            {
                                parent->_left = cur->_left;
                            }
                            else
                            {
                                parent->_right = cur->_left;
                            }
                        }
                        delete cur;
                    }
                    else//d
                    {
                        //找右树的最小节点去替代删除
                        Node* minRightParent = cur;
                        //cur->right一定不为空
                        Node* minRight = cur->_right;
                        //最小节点
                        while (minRight->_left)
                        {
                            minRightParent = minRight;
                            minRight = minRight->_left;
                        }
                        //替代
                        cur->_key = minRight->_key;
                        //minRight的左一定为空,但右不一定为空,minRightParent->_left不一定是minRight
                        if (minRight == minRightParent->_left)//删除5,找6
                        {
                            minRightParent->_left = minRight->_right;
                        }
                        else//删除7,找8
                        {
                            minRightParent->_right = minRight->_right;
                        }
                        delete minRight;
                    }
                    return true;
                }
            }
            return false;
        }
        void InOrder()
        {
            _InOrder(_root);
            cout << endl;
        }
        bool InsertR(const K& key)
        {
            return _InsertR(_root, key);
        }
        Node* FindR(const K& key)
        {
            return _FindR(_root, key);
        }
        bool EraseR(const K& key)
        {
            return _EraseR(_root, key);
        }
        //BSTree() = default;//C++11
        BSTree()
            : _root(nullptr)
        {}
        ~BSTree()
        {
            _Destroy(_root);
        }
        //BSTree(const BSTree& t)
        BSTree(const BSTree<K>& t)
        {
            _root = _Copy(t._root);
        }
        //BSTree& operator=(BSTree t)
        BSTree<K>& operator=(BSTree<K> t)//现代写法 t1 = t2
        {
            std::swap(_root, t._root);
            return *this;
        }
    private:
        Node* _Copy(Node* root)
        {
            if (root == nullptr)
            {
                return nullptr;
            }
            //深拷贝根
            Node* newRoot = new Node(root->_key);
            //递归拷贝左右子树
            newRoot->_left = _Copy(root->_left);
            newRoot->_right = _Copy(root->_right);
            //返回根
            return newRoot;
        }
        void _Destroy(Node* root)
        {
            if (root == nullptr)
            {
                return;
            }
            //后序
            _Destroy(root->_left);
            _Destroy(root->_right);
            delete root;
        }
        bool _EraseR(Node*& root, const K& key)
        {
            if (root == nullptr)
            {
                return false;
            }
            else if (root->_key < key)
            {
                return _EraseR(root->_right, key);
            }
            else if (root->_left > key)
            {
                return _EraseR(root->_left, key);
            }
            else
            {
                //删除
                Node* del = root;
                if (root->_left == nullptr)//ab
                {
                    root = root->_right;
                }
                else if (root->_right == nullptr)//ac
                {
                    root = root->_left;
                }
                else//d
                {
                    //替代
                    Node* minRight = root->_right;
                    while (minRight->_left)
                    {
                        minRight = minRight->_left;
                    }
                    root->_key = minRight->_key;
                    //大事化小,小事化了
                    return _EraseR(root->_right, minRight->_key);
                }
                delete del;
                return true;
            }
        }
        Node* _FindR(Node* root, const K& key)
        {
            if (root == nullptr)
            {
                return nullptr;
            }
            if (root->_key < key)
            {
                return _FindR(root->_right, key);
            }
            else if (root->_key > key)
            {
                return _FindR(root->_left, key);
            }
            else
            {
                return root;
            }
        }
        bool _InsertR(Node*& root, const K& key)
        {
            if (root == nullptr)
            {
                root = new Node(key);
                return true;
            }
            else
            {
                if (root->_key < key)
                {
                    return _InsertR(root->_right, key);
                }
                else if (root->_key > key)
                {
                    return _InsertR(root->_left, key);
                }
                else
                {
                    return false;
                }
            }
        }
        void _InOrder(Node* root)
        {
            if (root == nullptr)
            {
                return;
            }
            _InOrder(root->_left);
            cout << root->_key << " ";
            _InOrder(root->_right);
        }
    private:
        Node* _root = nullptr;
    };
}
